题目描述

题目译自 XXVI Olimpiada Informatyczna – III etap Zjazd obieżyświatów

旅行者协会计划举办盛大的旅行者聚会。然而，大多数旅行者忙于环球旅行，组织活动颇具挑战。协会有 $k$ 名旅行者，他们在由 $n$ 个庇护所和单向路径连接的世界中游历。旅行者每日更换庇护所，每个庇护所都有若干路径通往其他庇护所，确保他们不会停留。

已知宣布聚会当天每位旅行者的起始庇护所，请判断他们是否能在某庇护所相聚，若可行，计算最快需要多少天。

输入格式

第一行包含三个整数 $n, m, k$ $(2 \leq n \leq 250, n \leq m \leq n^2, 2 \leq k \leq n)$，分别表示庇护所数、路径数和旅行者数。庇护所编号为 $1$ 至 $n$。

第二行包含 $k$ 个整数 $s_1, s_2, \ldots, s_k$ $(1 \leq s_i \leq n)$，表示第 $i$ 位旅行者初始所在的庇护所。

接下来的 $m$ 行描述路径，每行包含两个整数 $a_j, b_j$ $(1 \leq a_j, b_j \leq n)$，表示第 $j$ 条路径从庇护所 $a_j$ 通往 $b_j$。路径不重复，每个庇护所至少有一条向外的路径。

输出格式

若旅行者无法相聚，输出一行 NIE。

否则，第一行输出 TAK，第二行输出一个整数，表示最少天数，使所有旅行者能在某庇护所相聚。

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

TAK
3

图示庇护所和路径，深色标记旅行者初始位置。旅行者可能的路线为：

$$1 \rightarrow 3 \rightarrow 4 \rightarrow 1, \quad 2 \rightarrow 3 \rightarrow 4 \rightarrow 1, \quad 3 \rightarrow 4 \rightarrow 5 \rightarrow 1. $$

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

NIE

附加样例

1. $n=5$，简单样例。
2. $n=250$，对于 $1 \leq i < n$，存在路径 $i \rightarrow i+1$；另有路径 $248 \rightarrow 250$ 和 $250 \rightarrow 249$。
3. $n=250$，循环 $1 \rightarrow \ldots \rightarrow 250 \rightarrow 1$，每庇护所可通往下一庇护所或自身（满足子任务 $2$ 条件）。
4. $n=250$，循环 $1 \rightarrow \ldots \rightarrow 250 \rightarrow 1$，每庇护所可通往下一庇护所或下下庇护所。

数据范围与提示

若仅第一行输出正确，可获 $40\%$ 的分数，但程序需在时间和内存限制内正常终止。

详细子任务附加限制及分值如下表所示。

子任务	附加限制	分值
$1$	$n \leq 10$	$20$
$2$	每庇护所可留原地，$n > 10$	$30$
$3$	无附加限制	$50$

正式地说，子任务 $2$ 保证每个庇护所存在路径返回自身。