Tourist's Journey

input/code.cpp: In function 'int main()':
input/code.cpp:65:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Serv>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |             for(int i=0;i<servad.size();i++){
      |                         ~^~~~~~~~~~~~~~
In file included from /usr/include/c++/13/bits/hashtable.h:35,
                 from /usr/include/c++/13/bits/unordered_map.h:33,
                 from /usr/include/c++/13/unordered_map:41,
                 from /usr/include/c++/13/functional:63,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:53,
                 from input/code.cpp:1:
/usr/include/c++/13/bits/hashtable_policy.h: In instantiation of 'std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Hash, _RangeHash, _Unused, __cache_hash_code>::__hash_code std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Hash, _RangeHash, _Unused, __cache_hash_code>::_M_hash_code(const _Key&) co...

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
typedef pair<ll,ll> pii;
vector<vector<pii>>g;
struct Serv{
    ll u,v,len;
};
const int MOD=1000*1000*1000+7;
int main()
{ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n,m,k;
    cin>>n>>m>>k;
    g.resize(n);
    for(int i=0;i<m;i++){
        int u,v;cin>>u>>v;
        u--;v--;
        g[u].push_back({v,1});
        g[v].push_back({u,1});
    }
    for(int i=1;i<n-1;i++){
        int u=i;
        while(u!=0 && u!=n-1 && g[u].size()==1){
            int v=g[u][0].first;
            g[u].clear();
            pii P={u,1};
            g[v].erase(remove(g[v].begin(),g[v].end(), P), g[v].end());
            u=v;
        }
    }
    for(int t=0;t<100;t++){
        for(int i=1;i<n-1;i++){
            if(g[i].size()==2){
                auto [u,lenU]=g[i][0];
                auto [v,lenV]=g[i][1];
                if(u==v)continue;
                g[i].clear();
                g[u].push_back({v,lenU+lenV});
                g[v].push_back({u,lenU+lenV});
                pii P={i,lenU};
                g[u].erase(remove(g[u].begin(),g[u].end(), P), g[u].end());
                pii P2={i,lenV};
                g[v].erase(remove(g[v].begin(),g[v].end(),P2),g[v].end());
            }
        }
    }
    vector<Serv> servad;
    for(ll i=0;i<n;i++){
        for(auto el:g[i]){
            if(i<el.first){
                Serv S;
                S.u=i;
                S.v=el.first;
                S.len=el.second;
                servad.push_back(S);
            }
            //cout<<i<<' '<<el.first<<' '<<el.second<<endl;
        }
    }
    vector<unordered_map<pii,ll>>kaugused(k+m+n+1);//sammul i olen tipus {x, serva kaud s}
    kaugused[0][{0,-1}]=1;
    for(int aeg=0;aeg<k;aeg++){
        for(auto [P,vaartus]:kaugused[aeg]){
            auto [x,eelmine]=P;
            for(int i=0;i<servad.size();i++){
                if(i==eelmine)continue;
                Serv serv=servad[i];
                int uusAeg=aeg+serv.len;
                if(x==serv.u){
                    pii P={serv.v,i};
                    kaugused[uusAeg][P]=(kaugused[uusAeg][P]+vaartus)%MOD;
                } else if(x==serv.v){
                    pii P={serv.u,i};
                    kaugused[uusAeg][P]=(kaugused[uusAeg][P]+vaartus)%MOD;
                }
            }
        }
    }
    ll summa=0;
    for(auto el:kaugused[k]){
        if(el.first.first==n-1)summa=(summa+el.second)%MOD;
    }
    cout<<summa<<endl;
    return 0;
}