{"raw_statement":[{"iden":"problem statement","content":"You are given a directed graph with $N$ vertices and $M$ edges. For $i = 1, 2, \\ldots, M$, the $i$\\-th edge is directed from vertex $s_i$ to vertex $t_i$.\nDetermine whether there is a permutation $P = (P_1, P_2, \\ldots, P_N)$ of $(1, 2, \\ldots, N)$ that satisfies both of the following conditions, and if there is, provide an example.\n\n*   $P_{s_i} \\lt P_{t_i}$ for all $i = 1, 2, \\ldots, M$.\n*   $L_i \\leq P_i \\leq R_i$ for all $i = 1, 2, \\ldots, N$."},{"iden":"constraints","content":"*   $2 \\leq N \\leq 2 \\times 10^5$\n*   $0 \\leq M \\leq \\min\\lbrace 4 \\times 10^5, N(N-1) \\rbrace$\n*   $1 \\leq s_i, t_i \\leq N$\n*   $s_i \\neq t_i$\n*   $i \\neq j \\implies (s_i, t_i) \\neq (s_j, t_j)$\n*   $1 \\leq L_i \\leq R_i \\leq N$\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $M$\n$s_1$ $t_1$\n$s_2$ $t_2$\n$\\vdots$\n$s_M$ $t_M$\n$L_1$ $R_1$\n$L_2$ $R_2$\n$\\vdots$\n$L_N$ $R_N$"},{"iden":"sample input 1","content":"5 4\n1 5\n2 1\n2 5\n4 3\n1 5\n1 3\n3 4\n1 3\n4 5"},{"iden":"sample output 1","content":"Yes\n3 1 4 2 5\n\n$P = (3, 1, 4, 2, 5)$ satisfies the conditions. In fact,\n\n*   for the first edge $(s_1, t_1) = (1, 5)$, we have $P_1 = 3 \\lt 5 = P_5$;\n*   for the second edge $(s_2, t_2) = (2, 1)$, we have $P_2 = 1 \\lt 3 = P_1$;\n*   for the third edge $(s_3, t_3) = (2, 5)$, we have $P_2 = 1 \\lt 5 = P_5$;\n*   for the fourth edge $(s_4, t_4) = (4, 3)$, we have $P_4 = 2 \\lt 4 = P_3$.\n\nAlso,\n\n*   $L_1 = 1 \\leq P_1 = 3 \\leq R_1 = 5$,\n*   $L_2 = 1 \\leq P_2 = 1 \\leq R_2 = 3$,\n*   $L_3 = 3 \\leq P_3 = 4 \\leq R_3 = 4$,\n*   $L_4 = 1 \\leq P_4 = 2 \\leq R_4 = 3$,\n*   $L_5 = 4 \\leq P_5 = 5 \\leq R_5 = 5$."},{"iden":"sample input 2","content":"2 2\n1 2\n2 1\n1 2\n1 2"},{"iden":"sample output 2","content":"No\n\nNo $P$ satisfies the conditions, so print `No`."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}