This page is still under construction.

Parts of this page are still being built. What you see may change.

Bamboo Forest

Time limit3sMemory limit1024 MB

Summary
Given a graph, decide whether every connected component is a bamboo: a tree with a trunk of at least 3 edges where each trunk vertex has 0 or 2 side leaves and all vertices lie within distance 1 of the trunk.
Level

Medium7 of 10

Topics
Graph, Tree, DFS, Implementation
Solved
No attempts yet

Problem

Jeonghwi defined a bamboo as follows. (It differs from the term Bamboo Tree used in graph theory.)

  • A bamboo is a kind of tree.
  • It has a trunk of length at least 3 (made up of at least 3 edges).
  • Vertices can branch off to both sides from a vertex on the trunk.
  • A vertex on the trunk cannot have 1 or 3 or more vertices branching off from it. (Only 0 or 2 are allowed.)
  • Every vertex must be at distance at most 1 from the trunk.

A bamboo forest is a forest made up only of bamboos.

Given a graph, determine whether it is a bamboo forest.

Sample 2 is not a bamboo forest because only 1 vertex branches off from vertex 2.

Sample 4 is not a bamboo forest because 3 vertices branch off from vertex 2.

Sample 5 is not a bamboo forest because among the vertices branching off from vertex 3 there is a vertex at distance 2 or more from the trunk.

Sample 6 is not a bamboo forest because no trunk of length at least 3 exists.

Sample 8 is not a forest.

Input

The first line gives the number of vertices and the number of edges N,MN, M, separated by a space.

From the second line, MM lines follow, each giving the two vertices u,vu, v connected by an edge, separated by a space.

Output

Print TAK if the given graph is a bamboo forest, and NIE otherwise.

Constraints

  • 1≤N≤100 0001 \leq N \leq 100\,000
  • 1≤M≤200 0001 \leq M \leq 200\,000
  • 1≤u,v≤N1 \leq u, v \leq N
  • No edge connects a vertex to itself.
  • No duplicate edge is given.

Examples5

  1. Example 1

    Input
    7 6
1 2
2 3
3 4
4 5
3 6
3 7
    Expected output
    TAK

  2. Example 2

    Input
    5 4
1 2
2 3
3 4
2 5
    Expected output
    NIE

  3. Example 3

    Input
    9 8
1 2
2 3
3 4
4 5
1 6
1 7
5 8
5 9
    Expected output
    TAK

  4. Example 4

    Input
    7 6
1 2
2 3
3 4
2 5
2 6
2 7
    Expected output
    NIE

  5. Example 5

    Input
    9 8
1 2
2 3
3 4
4 5
3 6
6 7
3 8
8 9
    Expected output
    NIE