#include <bits/stdc++.h> 

#define mod 1000000007;

int numberOfWays(int n, int k) {

vector<int>dp(n+1,0);

        dp[1]=k;

    dp[2]=k*k;

    for(int i=3;i<=n;i++){

        dp[i] = ((k - 1) * (dp[i - 1] + dp[i - 2])) % mod;

    }

    return dp[n];

}

#include <bits/stdc++.h> 

#include <unordered_map>

#include <list>

#include<set>

vector<int> dijkstra(vector<vector<int>> &vec, int vertices, int edges, int source) {

    unordered_map<int,list<pair<int,int>>>adj;

    for(int i=0;i<edges;i++){

        int u=vec[i][0];

        int v=vec[i][1];

        int w=vec[i][2];

        adj[u].push_back(make_pair(w,v));

        adj[v].push_back(make_pair(w,u));

    }

    vector<int>dis(vertices);

    for(int i=0;i<vertices;i++)

        dis[i]=INT_MAX;

    set<pair<int,int>>s;

    dis[source]=0;

    s.insert(make_pair(0,source));

    while(!s.empty()){

        auto top=*(s.begin());

        int nodedistance=top.first;

        int node=top.second;

        s.erase(s.begin());

        for(auto n:adj[node]){

            if(nodedistance+n.first<dis[n.second]){

                auto record=s.find(make_pair(dis[n.second],n.second));

                if(record!=s.end()){

                    s.erase(record);

                }

                dis[n.second]=nodedistance+n.first;

                s.insert(make_pair(dis[n.second],n.second));

            }

        }

    }

    return dis;

}

#include <map>

BinaryTreeNode<int>*target(BinaryTreeNode<int>* root, int start,

map<BinaryTreeNode<int>*,BinaryTreeNode<int>*>&childtoparent){

  BinaryTreeNode<int>*res=NULL;

  queue<BinaryTreeNode<int>*>q;

  q.push(root);

  childtoparent[root]=NULL;

  while(!q.empty()){

      BinaryTreeNode<int>*frontnode=q.front();

      q.pop();

      if(frontnode->data==start){

          res=frontnode;

      }

      if(frontnode->left){

          childtoparent[frontnode->left]=frontnode;

          q.push(frontnode->left);

      }

      if(frontnode->right){

          childtoparent[frontnode->right]=frontnode;

          q.push(frontnode->right);

      }

  }  

  return res;

}

int burntree(BinaryTreeNode<int>*target, 

map<BinaryTreeNode<int>*,BinaryTreeNode<int>*>childtoparent){

    map<BinaryTreeNode<int>*,bool>visited;

    queue<BinaryTreeNode<int>*>q;

    q.push(target);

    visited[target]=true;

    int ans=0;

    while(!q.empty()){

        bool flag=false;

        int size=q.size();

        for(int i=0;i<size;i++){

            BinaryTreeNode<int>*frontno=q.front();

            q.pop();

            if(frontno->left&&!visited[frontno->left]){

                flag=true;

                q.push(frontno->left);

                visited[frontno->left]=true;

            }

              if(frontno->right&&!visited[frontno->right]){

                  flag=true;

                q.push(frontno->right);

                visited[frontno->right]=true;

            }

            if(childtoparent[frontno]&&!visited[childtoparent[frontno]]){

                flag=true;

                q.push(childtoparent[frontno]);

                visited[childtoparent[frontno]]=true;

            }

        }

        if(flag==true)

        ans++;

    }

    return ans;

}

int timeToBurnTree(BinaryTreeNode<int>* root, int start)

{

    map<BinaryTreeNode<int>*,BinaryTreeNode<int>*>childtoparent;

    BinaryTreeNode<int>*targets=target(root,start,childtoparent);

     int ans=burntree(targets,childtoparent);

     return ans;

}