Comet OJ

C0534 [CEOI2011] Traffic

内存限制：256 MB 时间限制：5000 ms

题目描述

The center of Gdynia is located on an island in the middle of the Kacza river. Every morning thousands of cars drive through this island from the residential districts on the western bank of the river (using bridge connections to junctions on the western side of the island) to the industrial areas on the eastern bank (using bridge connections from junctions on the eastern side of the island).

The island resembles a rectangle, whose sides are parallel to the cardinal directions. Hence, we view it as an $A × B$ rectangle in a Cartesian coordinate system, whose opposite corners are in points $(0,0)$ and $(A,B)$.

On the island, there are $n$ junctions numbered from $1$ to $n$. The junction number $i$ has coordinates $(x_i,y_i)$. If a junction has coordinates of the form $(0,y)$, it lies on the western side of the island. Similarly, junctions with the coordinates $(A,y)$ lie on the eastern side. Junctions are connected by streets. Each street is a line segment connecting two junctions. Streets can be either unidirectional or bidirectional. No two streets may have a common point (except for, possibly, a common end in a junction). There are are no bridges or tunnels. You should not assume anything else about the shape of the road network. In particular, there can be streets going along the river bank or junctions with no incoming or outgoing streets.

Because of the growing traffic density, the city mayor has hired you to check whether the current road network on the island is sufficient. He asked you to write a program which determines how many junctions on the eastern side of the island are reachable from each junction on the western side.

输入格式

The first line of the standard input contains four integers $n, m$, $A$ and $B$ $(1 \le n \le 300000$, $0 \le m \le 900000$, $1 \le A,B \le 10^9)$. They denote the number of junctions in the center of Gdynia, the number of streets and dimensions of the island, respectively.

In each of the following $n$ lines there are two integers $x_i$, $y_i$ $(0 \le x_i \le A, 0 \le y_i \le B)$ describing the coordinates of the junction number $i$. No two junctions can have the same coordinates.

The next $m$ lines describe the streets. Each street is represented in a single line by three integers $c_i, d_i, k_i (1 \le c_i,d_i \le n, c_i \ne d_i, k_i \in \{1,2\})$. Their meaning is that junctions $c_i$ and $d_i$ are connected with a street. If $k_i = 1$, then this is a unidirectional street from $c_i$ to $d_i$. Otherwise, the street can be driven in both directions. Each unordered pair $\{c_i,d_i\}$ can appear in the input at most once.

You can assume that there is at least one junction on the western side of the island from which it is possible to reach some junction on the eastern side of the island.

Additionally, in test cases worth at least 30 points, $n,m \le 6000$.

输出

Your program should write to the standard output one line for each junction on the western side of the island. This line should contain the number of junctions on the eastern side that are reachable from that junction. The output should be ordered according to decreasing $y$-coordinates of the junctions.

样例

样例输入 1

5 3 1 3
0 0
0 1
0 2
1 0
1 1
1 4 1
1 5 2
3 5 2

样例输出 1

2
0
2

样例输入 2

12 13 7 9
0 1
0 3
2 2
5 2
7 1
7 4
7 6
7 7
3 5
0 5
0 9
3 9
1 3 2
3 2 1
3 4 1
4 5 1
5 6 1
9 3 1
9 4 1
9 7 1
9 12 2
10 9 1
11 12 1
12 8 1
12 10 1

样例输出 2

4
4
0
2

提示

image.png