Вася недавно придумал новое развлечение. Пусть дан связный ориентированный граф, состоящий из \(n\) вершин и \(2 \cdot (n - 1)\) рёбер, причём для каждого ребра \((u, v)\), существует ребро \((v, u)\). Иначе говоря, граф был получен из дерева, в котором каждое ребро было расщеплено на два противоположных ребра, ориентированных в разные стороны.

Назовем гаджетом такую пару рёбер \((e_1, e_2)\), что конец \(e_1\) совпадает с началом \(e_2\) или наоборот (в частности, два противоположных друг другу ребра — гаджет). Вася развлекается тем, что разбивает рёбра графа на непересекающиеся гаджеты. Конечно, ему легко удалось это сделать с исходным графом.

Васин друг Петя удалил из дерева \(2 \cdot k\) ориентированных рёбер. Таким образом, в графе осталось \(m = 2 \cdot (n - 1) - 2 \cdot k\) ориентированных ребер.

Теперь Вася хочет узнать, можно ли разбить оставшиеся ребра на непересекающиеся гаджеты, и, если можно, — найти это разбиение. Помогите ему!