P17059 [NWERC 2022] 土耳其烤肉披萨 / Kebab Pizza

译自 [Northwestern Europe Regional Contest (NWERC) 2022](https://2022.nwerc.eu) Problem K。 原题许可协议为 CC BY-SA。

Alice 喜欢披萨，并计划在生日时举办一场披萨派对，她会为所有客人做一个又大又圆的披萨。她知道朋友们在披萨口味上有点特别：Julie 不想要任何蔬菜，但喜欢披萨上有土耳其烤肉；Katy 绝不会吃上面有奶酪的披萨；Alice 自己非常喜欢披萨上放菠萝，而 Mickey 绝对讨厌菠萝。相反，Mickey 想在披萨上放意大利面，而其他所有人都觉得这很奇怪。类似的要求还有很多。简而言之，想满足所有人是不可能的。 作为折中，Alice 决定让每个人提前为自己的披萨片选择两种配料。只要某个人的披萨片恰好有他选择的两种配料，并且没有其他配料，这个人就会满意。注意，一个人可以选择同一种配料两次；在这种情况下，他只是会得到两倍分量的那种配料。 :::align{center}  ::: 图：样例输入 1 的示意图，其中一种可能方案在每片披萨上标出了两个配料编号。注意，每种配料只出现在一段连续的披萨片上。 在派对当天，Alice 发现擀开的披萨面团在厨房台面上占了太多空间，以至于她一次只能准备一种配料。为了优化流程并确保披萨能及时完成，她想让每种被选择的配料只拿出来一次，然后把它加到一段连续的披萨片上。注意，整个披萨在环形意义下也构成一段连续的披萨片。 请判断，是否可以按照这种方式准备披萨，同时满足所有人选择的配料组合。

输入包含： - 一行两个整数 $n$ 和 $k$（$3 \leq n,k \leq 10^5$），表示披萨片数量和可能配料种类数，配料编号为 $1$ 到 $k$。 - 接下来 $n$ 行，每行两个整数 $a$ 和 $b$（$1 \leq a,b \leq k$），描述第 $i$ 个人选择的两种配料。

如果 Alice 可以为每种被选择的配料选出一段连续的披萨片，使得最终披萨能够被分成 $n$ 片合适的披萨，则输出 `possible`。否则，输出 `impossible`。

【数据规模与约定】 对于所有数据，满足 $3 \leq n,k \leq 10^5$；$1 \leq a,b \leq k$。