Skip to content

11141: 【原1141】轨道交通系统

题目

题目描述

author: Kuan Yang 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1141

Description

s城的轨道交通系统由N个站点和M条路段组成,每条路段连接2个站点,站点标号为1到N,轨道交通是双向的。s城有k种列车运行线路,列车只能在现有的轨道路段上行驶,并且在每一个经过的站点都会停靠。现在s城的交通规划部门希望给列车站点重新编号,使得每一条列车运行线路经过的站点编号是严格单调的(单调递增或递减都可以,轨道是双向的)。站点的编号仍然是1到N中的某个数字,任意两个站点的新编号不能相同。

Input Format

输入文件有多组数据。

对于每组数据,第一行包含两个整数:N—车站的数量(2 ≤ N ≤ 100 000), M ——车站间路段的数量(1 ≤ M ≤ N – 1)。在以后的M行列出表示a与b两站之间的路段的成对的整数(a ≠ b, 1 ≤ a ≤ N, 1 ≤ b ≤ N)。随后在单独的一行列出一个正整数k——列车的路线数。在下面的k行中描述列车的路线图,每行一个。每个路线图是个整数数列——这些整数就是按列车所走的两个可能方向中的一条路线上的所有车站的号。路线图以0作为终点(结束)。

路线图中所有车站的号是不同的。在每条路线中车站的数量不少于两个。在每列列车的路线中任意两个相连车站都由路段连接。在所有路线图中车站的总量不超过200000个。可以存在哪列列车也不经过的车站和路段。 每组数据之间可能有一些空行。

Output Format

每组数据输出一行

如果无解,则输出“NO”(不含引号),如果有解,则输出“YES”(不含引号)。

Sample Input 1

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

Sample Output 1

NO

Explanation 1

轨道如下图所示

             1
             |
      2 -----4----- 3

三条列车线路是1--4--2、2--4--3、3--4--1,不存在使得每条线路经过的站点编号都严格单调的新编号方案。

Sample Input 2

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

Sample Output 2

YES

Explanation 2

轨道如下图所示

             1
             |
      2 -----5----- 4
             |
             3

将站点重新编号为1、4、2、5、3即可满足要求。

Hint

直接输出YES/NO,或者输出样例都是没有分的。 每个测试点最多有6组数据。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!