{"problem":{"name":"Cat Snuke and a Voyage","description":{"content":"In Takahashi Kingdom, there is an archipelago of $N$ islands, called Takahashi Islands. For convenience, we will call them Island $1$, Island $2$, ..., Island $N$. There are $M$ kinds of regular boat ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc079_a"},"statements":[{"statement_type":"Markdown","content":"In Takahashi Kingdom, there is an archipelago of $N$ islands, called Takahashi Islands. For convenience, we will call them Island $1$, Island $2$, ..., Island $N$.\nThere are $M$ kinds of regular boat services between these islands. Each service connects two islands. The $i$\\-th service connects Island $a_i$ and Island $b_i$.\nCat Snuke is on Island $1$ now, and wants to go to Island $N$. However, it turned out that there is no boat service from Island $1$ to Island $N$, so he wants to know whether it is possible to go to Island $N$ by using two boat services.\nHelp him.\n\n## Constraints\n\n*   $3 ≤ N ≤ 200$ $000$\n*   $1 ≤ M ≤ 200$ $000$\n*   $1 ≤ a_i < b_i ≤ N$\n*   $(a_i, b_i) \\neq (1, N)$\n*   If $i \\neq j$, $(a_i, b_i) \\neq (a_j, b_j)$.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$\n$a_1$ $b_1$\n$a_2$ $b_2$\n:\n$a_M$ $b_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc079_a","tags":[],"sample_group":[["3 2\n1 2\n2 3","POSSIBLE"],["4 3\n1 2\n2 3\n3 4","IMPOSSIBLE\n\nYou have to use three boat services to get to Island $4$."],["100000 1\n1 99999","IMPOSSIBLE"],["5 5\n1 3\n4 5\n2 3\n2 4\n1 4","POSSIBLE\n\nYou can get to Island $5$ by using two boat services: Island $1$ -> Island $4$ -> Island $5$."]],"created_at":"2026-03-03 11:01:14"}}