2108 . 殿壬玩遊戲
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 1
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 1
friendA
Hints
Problem Source
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~17 | 1 |