410647: GYM104068 L 逃跑路线

小团子周末一个人去玩密室逃脱，整个密室共有 n 个房间，由 m 个通道连接在一起，使得这 n 个房间相互连通。历尽千难万阻后，小团子终于破解出了谜题，得知了出去的密码。在密室的每个房间里都有一个旋钮，旋钮上的刻度为 ，根据小团子的记忆，第 i 个房间旋钮当前指向的刻度为 a_i，而根据密码需要将其调至 b_i，当所有房间的旋钮都调好后出口的门会立刻打开，这样小团子就可以润出去了。

小团子决定给自己加大难度，给自己添加了以下限制：当自己从房间 u 走到房间 v 时，小团子将会将房间 v 的旋钮向后旋转一下，即如果当前刻度为 x，旋转后的刻度为 x + 1。特别地，如果当前刻度为 k，旋转后的刻度为 1。

小团子想知道，在这样的限制下，有多少个房间可以作为起点，当小团子从这个房间出发时，存在一条路线使得小团子可以将所有房间的旋钮调好。

需要注意的是，在最开始时，小团子并不会旋转起点的旋钮。

第一行三个正整数 n, m, k（2 ≤ n ≤ 10⁶, n - 1 ≤ m ≤ 10⁶, 2 ≤ k ≤ 10⁶），表示房间数，通道数和旋钮刻度数。

接下来 n 行每行两个正整数 a_i 和 b_i（1 ≤ a_i, b_i ≤ k），表示第 i 个房间当前旋钮指向的刻度和最终所需指向的刻度。

接下来 m 行每行两个正整数 u 和 v（1 ≤ u, v ≤ n），满足 u ≠ v，表示房间 u 和房间 v 有一条直接相连的通道。

输入保证这 n 个房间相互连通，且两个房间至多由一条通道直接连接。

一行一个整数，表示可以作为起点的房间的数量。

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

1

4 3 4
2 4
1 2
3 1
1 4
1 2
2 3
3 4

4

在第一个样例中，仅有房间 1 可作为起点，一条可行路径为 。

在第二个样例中，所有房间都可作为起点。