在神秘的蠕虫之地有许多蠕虫屋。并非所有的屋子都有蠕虫居住。已知每个屋子最多住有一条蠕虫。一些屋子之间由路径相连。对于任意两个不同的屋子，存在且仅存在一条由路径组成的路线，使得路线上没有任何路径被重复经过。

有一天，所有的蠕虫决定在其中一个屋子聚会。它们约定，每小时每条蠕虫都会沿着离开当前屋子的路径移动，前往该路径另一端的屋子（在神秘的蠕虫之地，走过任何一条路径恰好需要一小时）。蠕虫们打算继续它们的旅程，直到它们全部在同一个屋子相遇（它们必须在同一时刻到达该屋子）。

不幸的是，蠕虫们没有预见到如果采用这种移动方式，聚会可能需要很长时间。有时甚至根本无法相遇。因此，蠕虫们请求你帮助验证它们是否能够聚会，如果可以，在最优情况下需要多长时间。

编写一个程序，完成以下任务：

• 从标准输入读取神秘的蠕虫之地的描述，
• 检查蠕虫是否能够聚会，如果可以，计算在最优情况下需要的时间，
• 将答案写入标准输出。

输入格式

标准输入的第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 50\,000$，$1 \le m \le 50\,000$），由一个空格分隔，分别表示神秘的蠕虫之地中屋子的数量和路径的数量。屋子编号为从 $1$ 到 $n$ 的自然数。接下来的 $m$ 行包含路径的描述。每行包含两个整数 $a$ 和 $b$（$1 \le a, b \le n$），由一个空格分隔，表示由给定路径连接的屋子编号。路径描述之后的一行包含一个整数 $k$（$2 \le k \le n$），表示居住在神秘的蠕虫之地的蠕虫数量。接下来的 $k$ 行，每行包含一个整数 $d$（$1 \le d \le n$），表示第 $k$ 条蠕虫居住的屋子编号。

输出格式

标准输出的第一行且仅包含一行，如果蠕虫无法按照规则移动并相遇，则输出单词 NIE（波兰语中的“不”），否则输出一个整数，表示所有蠕虫到达聚会地点所需的最短小时数。

样例

输入 1

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

输出 1

1