Color Graph VI

Let us associate each node of a simple undirected graph with some color.
Let x be a node and let c be a color. Denote by x(c) the set of all such nodes adjacent to x which color is c.
We say that a node x is stable when c1 is the color of x and |x(c1)| ≥ |x(c2)| for all colors c2c1.

We furthermore say that a set T = {u, v, w} of three pairwise distinct nodes u, v, w is a stable triple if the following holds:

A distance from a node x in the graph to a stable triple T is equal to the minimum possible length of a path which connects x to some node in T.

In this problem, one prominent node, called base node, is specified in the graph.

     


Image 1. Three graphs corresponding to Example 1, 2, and 3 below. Each base node is highlighted by an additional circle.
For each graph we specify a distance from the base node and the list of stable triples in that distance.
a) Distance 0: (0, 1, 4), (4, 5, 6); distance 1: (0, 1, 5), (1, 5, 6), (5, 6, 7); distance 2: (6, 7, 8).
b) Distance 0: (2, 6, 7); distance 1: (1, 6, 7), (3, 7, 6), (4, 7, 6), (6, 7, 9).
c) Distance 1: (3, 7, 11), (4, 7, 11), (6, 10, 11), (7, 11, 8), (8, 11, 10); distance 2: (0, 3, 7), (2, 3, 7), (1, 4, 7), (5, 4, 7), (3, 7, 10), (4, 7, 10), (6, 10, 7); distance 3: (0, 3, 4), (2, 3, 4), (1, 4, 3), (3, 4, 5).

The task

You are given a graph, a color of each its node and a base node in the graph. Determine the distances from the base node to all stable triples in the graph.


Input

The first input line contains four integers N, E, C, S separated by space and representing (in this order) the number of nodes in the graph, the number of edges in the graph, the number of node colors in the graph and the base node label. We assume that the nodes are labeled 0, 1, ..., N−1.
The next line contains N integers, separated by spaces, which represent the list of colors of particular nodes. The colors are listed in ascending order of node labels. The first integer represents the color of node 0, the second integer represents the color of node 1, etc. We assume that the colors are labeled 0, 1, ..., C−1.
Next, there are N −1 text lines, each specifies one edge in the graph. The line contains two integers, separated by space, which represent the labels of the edge endnodes. The edges are listed in no particular order.
It holds, 2 ≤ N ≤ 104, 3 ≤ E ≤ 5 × 105, 3 ≤ C ≤ 100. The input graph is connected and it contains at least one stable triple.

Output

The output contains one or more lines. Each line contains two values d, f separated by space. Value f is the number of stable triples in the graph which distance from the base node is exactly d. If f equals 0 the line is not printed. The lines are sorted in ascending order of d values.

Example 1

Input
9 16 4 4
2 1 3 2 1 1 0 0 0
0 1
0 2
0 3
1 2
1 4
1 5
2 3
2 5
2 6
2 7
3 7
3 8
4 5
5 6
6 7
7 8
Output
0 2
1 3
2 1
The graph in Example 1 is depicted in Image 1 a).

Example 2

Input
10 22 3 2
2 0 0 1 1 2 0 1 2 1
1 2 
1 5 
1 6
2 5
2 6
5 6
6 7
0 3
0 4
0 7
0 8
0 9
3 4
3 7
3 8
3 9
4 7
4 8
4 9
7 8
7 9
8 9
Output
0 1
1 4
The graph in Example 2 is depicted in Image 1 b).

Example 3

Input
13 18 6 12
0 5 0 1 1 5 4 1 2 3 4 2 3
0 2
0 3
1 4
1 5
2 3
3 4
4 5
3 7
4 7
6 9
6 10
7 10
7 11
8 11
8 12
9 10
10 11
11 12
Output
1 5
2 7
3 4
The graph in Example 3 is depicted in Image 1 c).

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set