using Node_t = int;
using Nodes_t = std::vector<::Node_t>;
using NodesQueue_t = std::queue<::Node_t>;
using NodesMap_t = std::unordered_map<::Node_t, ::Nodes_t>;

constexpr Node_t nodeRoot{1};
constexpr Node_t nodeDummy{0};

bool IsValidTreeCut(
    ::NodesMap_t &,
    ::Node_t const,
    ::Node_t const  
);

bool IsNodesCountEven(
    ::NodesMap_t &,
    ::Node_t const
);

int evenForest(
    ::Node_t const nodesCount,
    ::Node_t const edgesCount,
    ::Nodes_t const & nodesFrom,
    ::Nodes_t const & nodesTo
){
    using namespace std;
    auto nodeToNeighbours{::NodesMap_t{}};
    nodeToNeighbours[::nodeDummy] = ::Nodes_t{};
    for(size_t idx{0}; idx < nodesFrom.size(); ++idx){
        nodeToNeighbours[nodesFrom.at(idx)].emplace_back(nodesTo.at(idx));
        nodeToNeighbours[nodesTo.at(idx)].emplace_back(nodesFrom.at(idx));
    }
    auto qBfs{::NodesQueue_t{}};
    auto nodesVisited{vector<bool>(nodeToNeighbours.size(), false)};
    qBfs.push(::nodeRoot);
    nodesVisited.at(::nodeRoot) = true;
    nodesVisited.at(::nodeDummy) = true;
    auto nodeCurrent{numeric_limits<::Node_t>::max()};
    auto cutsCount{0};
    while(!qBfs.empty()){
        nodeCurrent = qBfs.front();
        qBfs.pop();
        for(auto const nodeNext: nodeToNeighbours.at(nodeCurrent)){
            if(nodesVisited.at(nodeNext)){
                continue;
            }
            qBfs.push(nodeNext);
            nodesVisited.at(nodeNext) = true;
            if(::IsValidTreeCut(nodeToNeighbours, nodeCurrent, nodeNext)){
                ++cutsCount;
            }
        }
    }
    return cutsCount;
}

bool IsValidTreeCut(
    ::NodesMap_t & nodeToNeighbours,
    ::Node_t const nodeParent,
    ::Node_t const nodeNewRoot 
){
    using namespace std;
    auto & nodesNeighboursA{nodeToNeighbours.at(nodeNewRoot)};
    auto nodeParentIter{find(begin(nodesNeighboursA), end(nodesNeighboursA),
        nodeParent)};
    if(nodeParentIter == end(nodesNeighboursA)){
        return false;
    }
    *nodeParentIter = ::nodeDummy; 
    auto & nodesNeighboursB{nodeToNeighbours.at(nodeParent)};
    auto nodeNewRootIter{find(begin(nodesNeighboursB), end(nodesNeighboursB),
        nodeNewRoot)};
    if(nodeNewRootIter == end(nodesNeighboursB)){
        return false;
    }
    *nodeNewRootIter = ::nodeDummy;
    if(::IsNodesCountEven(nodeToNeighbours, nodeNewRoot)){
        return true;
    }
    *nodeParentIter = nodeParent;
    *nodeNewRootIter = nodeNewRoot;
    return false;
}

bool IsNodesCountEven(
    ::NodesMap_t & nodeToNeighbours,
    ::Node_t const nodeNewRoot
){
    using namespace std;
    auto qBfs{::NodesQueue_t{}};
    auto nodesVisited{vector<bool>(nodeToNeighbours.size(), false)};
    qBfs.push(nodeNewRoot);
    nodesVisited.at(nodeNewRoot) = true;
    nodesVisited.at(nodeDummy) = true;
    auto nodeCurrent{numeric_limits<::Node_t>::max()};
    size_t nodesCount{1};
    while(!qBfs.empty()){
        nodeCurrent = qBfs.front();
        qBfs.pop();
        for(auto const nodeNext: nodeToNeighbours.at(nodeCurrent)){
            if(nodesVisited.at(nodeNext)){
                continue;
            }
            qBfs.push(nodeNext);
            ++nodesCount;
            nodesVisited.at(nodeNext) = true;   
        }
    }
    return nodesCount % 2 == 0;
}