我们可以分两种情况讨论
1.如果原图存在一条1到n的有向通路。那么现在就有一个1到n的最大值x，我们可以通过转置图让x变小，但是不可能转置次数超过log（x+1）次
所以我们可以建20层分层图,每一次间的值就是2^(k-1)+1，然后跑最短路就可以了，然后每一次n点中的最小值就是答案
2.如果发现没办法到n，那么说明原图中不存在一条1到n的通路
那么我们假设进行了x次图转置，走的路径长度是y，那么我们肯定首先要保证x最小，因为y是肯定小于x的，在x相等的情况下，就要找y最小
然后我们建两层的分层图再按{x，y}跑最短路就好了

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<set>
#include<map>
#include<string>
#include<string.h>
#define maxn 5005000
#define ll long long
#include<vector>
#include<queue>
using namespace std;
const ll mod=998244353;
const ll inf=1e18;
ll qpow(ll x,ll n)
{
    ll ans=1;
    while(n)
    {
        if(n&1) ans*=x,ans%=mod;
        x*=x;x%=mod;
        n/=2;
    }
    return ans;
}
struct node
{
    ll to,w;
    friend bool operator<(node a,node b)
    {
        return a.w>b.w;
    }
};
ll dis[maxn],vis[maxn];
ll head[maxn],cnt;
struct E
{
    ll to,w,next;
}e[maxn*2];
void add(ll u,ll v,ll w)
{
    e[cnt].to=v;
    e[cnt].w=w;
    e[cnt].next=head[u];
    head[u]=cnt++;
}
struct nd
{
    ll x,y;
}edge[1050000];
priority_queue<node>q;
ll n,m;
void dijk(ll st)
{
    for(ll i=0;i<=22*n+100;i++) vis[i]=0,dis[i]=inf;
    dis[st]=0;
    q.push({st,0});

    while(!q.empty())
    {
        ll u=q.top().to;q.pop();
        if(vis[u]==1) continue;
        vis[u]=1;
        // printf("dis[%lld]=%lld\n",u,dis[u]);
        for(ll i=head[u];i!=-1;i=e[i].next)
        {
            ll v=e[i].to,w=e[i].w;
            if(dis[u]+w<dis[v])
            {
                dis[v]=dis[u]+w;
                //printf("  dis[%lld]=%lld w=%lld\n",v,dis[v],w);
                q.push({v,dis[v]});
            }
        }
    }
}
#define maxn1 1050000
struct nd1
{
    ll x,y;
    friend bool operator<(nd1 a,nd1 b)
    {
        if(a.x==b.x) return a.y>b.y;
        else return a.x>b.x;
    }
}dis1[maxn1];
struct node1
{
    ll to,x,y;
    friend bool operator<(node1 a,node1 b)
    {
        if(a.x==b.x) return a.y>b.y;
        else return a.x>b.x;
    }
};
priority_queue<node1>q1;
vector<node1>e1[maxn1];
ll vis1[maxn1];
void dijk1(ll st)
{
    for(ll i=0;i<=n*3+100;i++) dis1[i]={inf,inf},vis1[i]=0;
    vis1[st]=0;dis1[st]={0,0};
    q1.push({st,0,0});
    while(!q1.empty())
    {
        //printf("1111\n");
        ll u=q1.top().to;q1.pop();
        if(vis1[u]==1) continue;
        vis1[u]=1;
        //printf("u=%lld x=%lld y=%lld\n",u,dis1[u].x,dis1[u].y);
        for(node1 i:e1[u])
        {
            ll v=i.to,x=i.x,y=i.y;
            if(dis1[u].x+x<dis1[v].x||((dis1[u].x+x==dis1[v].x)&&(dis1[u].y+y<dis1[v].y)))
            {
                dis1[v]={dis1[u].x+x,dis1[u].y+y};
                //printf("  v=%lld x=%lld y=%lld\n",v,dis1[v].x,dis1[v].y);
                q1.push({v,dis1[v].x,dis1[v].y});
            }
        }
    }
}
int main()
{

    memset(head,-1,sizeof(head));cnt=0;
    scanf("%lld %lld",&n,&m);
    for(ll i=1;i<=m;i++)
    {
        ll u,v;
        scanf("%lld %lld",&u,&v);
        edge[i]={u,v};
        for(ll j=1;j<=20;j++)
        {
            if(j%2==1)
            {
                add(n*(j-1)+u,n*(j-1)+v,1);
                if(j!=20)add(n*(j-1)+v,n*j+u,(1ll<<(j-1))+1);
            }
            else
            {
                add(n*(j-1)+v,n*(j-1)+u,1);
                if(j!=20)add(n*(j-1)+u,n*j+v,(1ll<<(j-1))+1);
            }
        }
    }
    dijk(1);
    ll ans=inf;
    for(ll i=n;i<=20*n;i+=n) ans=min(ans,dis[i]);
    if(ans!=inf)
    {
        printf("%lld\n",ans);
        return 0;
    }
    for(ll i=1;i<=m;i++)
    {
        ll u=edge[i].x,v=edge[i].y;
        e1[u].push_back({v,0,1});
        e1[v].push_back({n+u,1,1});
        e1[n+v].push_back({n+u,0,1});
        e1[n+u].push_back({v,1,1});
    }
    /*for(ll i=1;i<=2*n;i++)
    {
        printf("u=%lld\n",i);
        for(node1 j:e1[i]) printf("%lld ",j.to);
        printf("\n");
    }*/
    dijk1(1);
    nd1 ans1;
    if(dis1[n].x<dis1[2*n].x) ans1=dis1[n];
    else if(dis1[n].x>dis1[2*n].x) ans1=dis1[2*n];
    else if(dis1[n].y<dis1[2*n].y) ans1=dis1[n];
    else ans1=dis1[2*n];
    /*if(dis1[n]<dis1[2*n]) ans1=dis1[n];
    else ans1=dis1[2*n];
    printf("dis1[n].x=%lld dis1[n].y=%lld\n",dis1[n].x,dis1[n].y);
    printf("dis1[2n].x=%lld dis1[2n].y=%lld\n",dis1[2*n].x,dis1[2*n].y);
    printf("%lld %lld\n",ans1.x,ans1.y);*/
    printf("%lld\n",(qpow(2,ans1.x)-1+ans1.y+mod)%mod);
    return 0;
}
/*
23 22
2 1
2 3
4 3
4 5
6 5
6 7
8 7
8 9
10 9
10 11
12 11
12 13
14 13
14 15
16 15
16 17
18 17
18 19
20 19
20 21
22 21
22 23
*/