| 问题描述 |
|---|
有 n 名勇者和 m 条恶龙，勇者的编号从 1 到 n，恶龙的编号从 1 到 m。勇者和恶龙的战斗力各不相同。 小罗认为，在一场对战中，战斗力较高的那方总能获胜，而且把不能战胜任何恶龙的勇者称为「得过且过的勇者」。 但是小罗目前只知道部分勇者和恶龙间的胜负关系，当不能确定两个勇者或恶龙的战胜关系时，就认为他们都有可能战胜对方。 小罗希望你找出全部「得过且过的勇者」，同时他也想让你告诉他每个勇者最多可以战胜多少条恶龙。
|
| 输入描述 |
第一行包含三个正整数 n、m、q。（1 ≤ n、m ≤ 1000，1 ≤ q ≤ 3000） 接下来 q 行形如： 1 x y：表示勇者 x 能够战胜勇者 y 。保证 x != y。 2 x p：表示勇者 x 能够战胜恶龙 p 。 3 p q：表示恶龙 p 能够战胜恶龙 q 。保证 p != q。 4 p x：表示恶龙 p 能够战胜勇者 x 。 保证数据是合法的，即不会出现战斗力低的勇者或恶龙战胜战斗力高的勇者或恶龙。 |
| 输出描述 |
第一行输出一个整数 k 表示「得过且过的勇者」的数量。 第二行按从小到大的顺序输出 k 个整数，分别表示每个「得过且过的勇者」的编号，每输出一个数字后都要输出一个空格；特别的，如果没有「得过且过的勇者」，本行输出 -1。 第三行输出 n 个整数，分别表示每个勇者最多可以战胜恶龙的数量，每输出一个数字后都要输出一个空格。
|
| 样例输入复制样例 |
2 2 3 4 1 1 4 2 1 3 2 1 |
| 样例输出 |
1 1 0 2 |
| 提示说明 |
【恶龙 1】战胜了【勇者 1】，证明【恶龙 1】的战斗力高于【勇者 1】的战斗力。 【恶龙 2】战胜了【勇者 1】，证明【恶龙 2】的战斗力高于【勇者 1】的战斗力。 【恶龙 2】战胜了【恶龙 1】，证明【恶龙 2】的战斗力高于【恶龙 1】的战斗力。
故【勇者 1】是「得过且过的勇者」。 由于我们无法确定【勇者 2】和【恶龙 1】【恶龙 2】的胜负关系，所以【勇者 2】最多可能战胜 2 条恶龙。 题目来源：JMU第八届天梯校选 |
| 相关 |