33621번 - 피돌이 vs 피붕이

문제

각 정점에서 나가는 간선이 최대 2개이고 정점이 $N$개인 유향 비순환 그래프(DAG)가 주어진다. 초기에 그래프의 $i$번 정점 위에는 $a_i$개의 돌멩이가 놓여있다. 피돌이와 피붕이가 이 그래프를 이용해 다음과 같은 게임을 한다.

• 선공부터 번갈아 가며 다음을 반복한다.
• 간선 1개를 고른다. 고른 간선의 출발 정점과 도착 정점을 각각 $u,ドル $v$라고 하자. $u$에서 돌멩이 1ドル$개 또는 2ドル$개를 골라 $v$로 옮긴다.
• 자신의 차례에 위 시행을 할 수 없게 된 사람이 지게 된다.

다른 문제들의 지문에서 알 수 있듯이 피돌이가 이겼다. 그래프가 주어질 때 피돌이가 선공이었을지 후공이었을지 판단해 보자. 단, 둘 다 최선의 전략을 사용했다고 가정한다.

입력

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. $(1 \leq T \leq 10\ 000)$

각 테스트 케이스의 첫째 줄에 그래프의 정점 개수와 간선 개수 $N,ドル $M$이 공백을 두고 주어진다. $(1 \leq N \leq 200\ 000; 0 \leq M \leq 2N-3)$

각 테스트 케이스의 둘째 줄에 각 정점에 놓인 돌멩이의 개수를 나타내는 $N$개의 정수 $a_1, a_2, \cdots, a_N$이 공백을 두고 주어진다. $(1 \leq a_i \leq 10^9)$

각 테스트 케이스의 다음 $M$줄에 각 간선의 출발 정점과 도착 정점 $u_i,ドル $v_i$가 공백을 두고 주어진다. $(1\leq u_i < v_i \leq N)$

중복간선이 없고 모든 정점의 외차수(outdegree)가 2 이하임이 보장된다. 즉, 서로 다른 두 정수 $i, j$에 대해 항상 $(u_i, v_i) \neq (u_j, v_j)$이며 $u_i=x$를 만족하는 $i$가 3개 이상이 되게하는 $x$는 존재하지 않는다.

모든 테스트 케이스에서 $N$의 합은 200ドル\ 000$을 넘지 않는다.

출력

각 테스트 케이스의 첫째 줄에 피돌이가 선공이었다면 First, 후공이었다면 Second를 출력한다.

제한

힌트