题目描述

教务处针对 $n$ 门课程设置了 $m$ 条约束条件，其中的第 $i$ 条约束要求在学习第 $y_i$ 门课程之前，必须先修完第 $x_i$ 门课程。

请判断这些约束条件是否存在矛盾。如果没有矛盾输出 Valid，否则输出 Invalid。

输入格式

• 第一行：两个整数表示 $n$ 与 $m$
• 第二行到第 $m+1$ 行：第 $i+1$ 行有两个整数表示 $x_i$ 与 $y_i$

输出格式

• 如果可行输出 Valid 否则输出 Invalid

数据范围

• $50\%$ 的数据，$1\leq n\leq 100$，$1\leq m\leq 10000$
• $100\%$ 的数据，$1\leq n\leq 200,000$，$1\leq m\leq 500,000$

样例数据

输入:

3 3
1 2
2 3
3 1

输出:

Invalid

输入:

4 4
1 2
2 3
3 4
1 4

输出:

Valid