Colosseo

Mr. Chopsticks keeps N monsters, numbered from 1 to N. In order to train them, he holds N * (N - 1) / 2 competitions and asks the monsters to fight with each other. Any two monsters fight in exactly one competition, in which one of them beat the other. If monster A beats monster B, we say A is stronger than B. Note that the “stronger than” relation is not transitive. For example, it is possible that A beats B, B beats C but C beats A.

After finishing all the competitions, Mr. Chopsticks divides all the monsters into two teams T1 and T2, containing M and N – M monsters respectively, where each monster is in exactly one team. Mr. Chopsticks considers a team of monsters powerful if there is a way to arrange them in a queue (A1, A2, …, Am) such that monster Ai is stronger than monster Aj for any 1<=i<j<=m. Now Mr. Chopsticks wants to check whether T1 and T2 are both powerful, and if so, he wants to select k monsters from T2 to join T1 such that the selected monsters together with all the monsters in T1 can still form a powerful team and k is as large as possible. Could you help him?

The input contains multiple test cases. Each case begins with two integers N and M (2 <= N <= 1000, 1 <= M < N), indicating the number of monsters Mr. Chopsticks keeps and the number of monsters in T1 respectively. The following N lines, each contain N integers, where the jth integer in the ith line is 1 if the ith monster beats the jth monster; otherwise, it is 0. It is guaranteed that the ith integer in the jth line is 0 iff the jth integer in the ith line is 1. The ith integer in the ith line is always 0. The last line of each case contains M distinct integers, each between 1 and N inclusively, representing the monsters in T1. The input is terminated by N = M = 0.

For each case, if both T1 and T2 are powerful, output “YES” and the maximum k; otherwise, output “NO”.

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

YES 1
NO
YES 1

In the third example, Mr. Chopsticks can let the monster numbered 4 from T2 join into T1 to form a queue (1, 2, 4).

SYSU

2016 Multi-University Training Contest 7