TopCoder

User's AC Ratio

NaN% (0/0)

Submission's AC Ratio

NaN% (0/0)

Description

殿壬是個天才兒童,他在一個月大的時候就學會數數、六個月大的時候就學會乘法跟除法、一歲時學會寫程式、一歲又六個月時養了可愛的拉不拉多、一歲又十個月時養了可愛的貓咪、兩歲時發明了「吃餅乾」的遊戲,而現在要講的,是殿壬一歲大時的故事。

這一天殿壬看到他的友人A和友人B在玩一種遊戲,規則如下:

  • 玩家們在一個有向連通圖上輪流移動一個共用的棋子

  • 此圖為一個 directed cactus(see the note below)

  • 所有環都為偶環

  • 每條邊的邊權不是1就是0

  • 先手希望經過的得分(經過的總邊權和)越多越好,後手則相反

  • A,B兩人都很聰明,會選擇對自己最有利的策略

  • 當棋子返回起點後即結束(有可能此遊戲不會結束)

  • 勝負的定義為先手若可以得分無限大,則先手獲勝,反之則後手獲勝 (see the note below)

殿壬在聽懂了規則和起始棋子位置後一下就說他知道誰會贏了,身為友人C的你,對於殿壬的才智感到驚嘆,不甘示弱的你也想要寫個程式來證明自己。
Note1:
directed cactus definition: 有向圖上,每條邊隸屬於恰好一個有向簡單環。另一種說法:許多有向環,相互銜接成樹狀,接縫恰好是一點。

Note2:
對於先手獲勝條件只有:在不回起點的條件下一直經過正權邊
對於後手:1.回起點,遊戲結束2.在不回起點的情況下,且在一定步數之後,不再經過任何正權邊

Input Format

輸入的第一行有一正整數$t$,代表有$t$筆輸入

對於每筆測試資料

第一行有三個正整數$n, m, s$,代表總共有$n$個點,以及$m$個簡單環,和起始點為$s$

接下來有$m$行,每行會有一正整數$num_i$代表此簡單環的點數,接下來有$2\times num_i$個整數$v_1, e_{12}, v_2, ..., v_{num_{i-1}}, e_{num_{i-1}num_{i}}, v_{num_i}, e_{num_{i}1}$,代表$v_i$ 和$v_{i + 1}$有一權重為$e_{ii+1}$的邊($v_{num_i}$為和$v_1$間有權重為$e_{numi1}$的邊)

  • $1\leq n\leq 10^ 5$
  • $1\leq m, s\leq n$
  • $num_i$為正偶數
  • $1\leq v_i\leq n$
  • $0\leq e_{ii+1}\leq 1$

對於所有測試資料

  • $n$的總和$\leq 10^ 5$
  • $m$的總和$\leq 10^ 5$

保證input合法

Output Format

請輸出$t$行
第$i$行若第$i$筆測試資料
先手(友人A)會贏則輸出friendA
若後手(友人B)會贏則輸出 friendB

Sample Input

2
4 1 1
4 1 0 2 0 3 0 4 0
5 2 1
4 1 0 2 0 3 0 4 0
2 3 0 5 1

Sample Output

friendB
friendA

Hints

Problem Source

Subtasks

No. Testdata Range Score
1 0~17 1

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 1
2 1000 65536 262144 1
3 1000 65536 262144 1
4 1000 65536 262144 1
5 1000 65536 262144 1
6 1000 65536 262144 1
7 1000 65536 262144 1
8 1000 65536 262144 1
9 1000 65536 262144 1
10 1000 65536 262144 1
11 1000 65536 262144 1
12 1000 65536 262144 1
13 1000 65536 262144 1
14 1000 65536 262144 1
15 1000 65536 262144 1
16 1000 65536 262144 1
17 1000 65536 262144 1