As a landlocked country in central and
southern Africa , the political situation has been relatively stable since the
implementation of multi-party elections in ZBA in 1991. But the ZBA parliament
passed the 90 day emergency order issued by the president on 11 days of local
time . The tension is that the patriotic
team led by the government troops and NPG leaders founded by aborigines started,
in addition to the unlawful insurgents of illegal militants.
Chinese peacekeepers are going to the town of Kerver to seek
Chinese foreign aid engineers.
The military map shows that there are many checkpoints in the war zone. It can be modeled as a directed graph: nodes represent checkpoints , and edges represents the roads. The goal is that the less peacekeepers pass the checkpoints, the safer it will be.
The first line of the input
contains one integer T, which is the number of test cases (1<=T<=5). Each test case
* Line 1: N M A B
(2 ≤ N ≤ 100)
N and M denote the
number of nodes and edges in the directed graph respectively. The checkpoints are labeled 1, 2, ..., N, where chinese peacekeepers at node A and foreign aid engineers at node B.
*Line 2~m+1: Xi Yi (i=1, …., M)
followed by M lines containing two integers Xi and Yi (1 ≤ Xi, Yi ≤ N),
denoting that there is a directed edge from node Xi to node Yi in
each test case generate a single line: a single integer that the
minimum number of checkpoints . If a checkpoint
is passed on the way back and forth , it will be counted only once.
1 6 10 1 5 1 2 2 1 2 3 3 5 5 4 4 2 1 6 6 5 5 3 3 2