#P7263. 我也许做了假题目
我也许做了假题目
我也许做了假题目
题目描述
YMDragon 想做 NOIP 2016 的「天天爱跑步」,请 XLightGod 给他一份题目和数据,结果收到的是这个版本。
地图是一棵有 个结点、 条边的仙人掌,即连通的无向图,每条边至多属于一个简单环。结点编号为 至 。保证所有环都包含奇数个结点,因此任意两个结点之间的最短路径唯一。
有 名玩家,第 名玩家的起点为 ,终点为 。所有玩家在第 秒同时出发,以每秒经过一条边的速度沿各自的最短路径前进,中途不停,抵达终点后结束。
每个结点 都有一名观察员,只在第 秒观察。若一名玩家恰好在该时刻到达结点 ,他就会被观察到。玩家在出发时位于起点,在到达终点的那一刻也可以被观察到,但结束后不能继续被观察到。
求每个结点的观察员能观察到多少名玩家。
输入格式
第一行有三个整数 。其中, 表示仙人掌的结点数,同时也是观察员的数量; 表示图的边数; 表示玩家的数量。
接下来 行,每行两个整数 ,表示点 和点 之间有一条边。
接下来一行有 个整数,其中第 个整数为 ,表示结点 的观察员观察的时刻。
接下来 行,每行两个整数 ,表示一个玩家的起点和终点。
输出格式
输出一行 个整数,第 个整数表示结点 的观察员能观察到的玩家数量。
样例
样例 1
8 8 2
1 2
1 3
2 4
3 5
4 5
2 6
4 7
3 8
2 1 3 1 2 0 0 4
7 8
6 8
1 1 2 1 1 1 1 2
样例 2
见下发文件中的 problem2.in/ans。
样例 3
见下发文件中的 problem3.in/ans。
数据范围
| 测试点 | 限制 |
|---|---|
| 1–4 | |
| 5–8 | , |
| 9–12 | , |
| 13–20 |
对于所有测试点,。