While on a journey in search of her mother's home, Mayoi Hachikuji continuously finds herself lost within the massive network of roads of her city.
In this city, there are
With her past experience in life leading her to avoid as many trucks as possible, Mayoi asks you the following question:
If I start at intersection
and take at most steps, what is the minimal number of passing trucks per minute (denoted by ), over all the intersections I could possibly traverse (denoted by )?
Being a ghost who cannot pass through walls, Mayoi asks you a second question to help her save time:
For the same starting intersection
, at how many possible different intersections could I finish my journey by taking exactly steps (denoted by )?
Note: If Mayoi finds herself at an intersection with no outgoing roads and has yet to take exactly
Input Specification
The first line of input contains two space-separated integers
The second line contains
The next
The next line of input contains the integer
The next
Constraints
For all subtasks:
Subtask | Points | |||
---|---|---|---|---|
Output Specification
For each of Mayoi's queries, output the desired answers (c d
.
Sample Input 1
3 2
3 1 2
1 2
3 1
4
1 0
3 0
3 1
3 3
Sample Output 1
3 1
2 1
2 1
1 0
Explanation 1
The graph of Sample Input
For Mayoi's first two queries, she does not take any steps. Therefore, the minimum rate of passing trucks is that of the starting intersection. The starting point is also the only possible destination point.
For her last query, the intersection with the lowest rate of trucks
Sample Input 2
4 4
5 7 3 8
4 1
2 3
2 4
3 1
2
2 1
4 4
Sample Output 2
3 2
5 0
Comments