1

2 1 0

1

0

1

3 3 0

1

2

1
2
3
4
5
6

7 13 5
1 3
4 5
5 4
6 1
2 2

1

443723615

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>

using namespace std;

#define MOD 998244353

struct Node{
    int next, to;
}NDS[100010];

int cnt = 0;
int head[100010];

void add(int a, int b){ 
    NDS[cnt].to = b;
    NDS[cnt].next = head[a];
    head[a] = cnt++;
}

vector<int> P;
int DP[2][100010];

map<int, int> Dict;

int main() {
    memset(head,-1,sizeof(head));
    int n,m,k;
    cin >> n >> m >> k;
    for(int i = 1; i<=k; i++){
        int a,b;
        cin >> a >> b;
        
        int ida, idb;
        if(!(ida = Dict[a])) P.push_back(Dict[a] = ida = Dict.size());
        if(!(idb = Dict[b])) P.push_back(Dict[b] = idb = Dict.size());
        if(ida != idb) add(idb,ida);
    }
    
    if (!Dict[1]) P.push_back(Dict[1] = Dict.size());
    int Nc = Dict.size();
    int Fc = n - Nc, idf = Dict.size()+1;
    
    int sum = 1, sum2 = 0;
    DP[0][Dict[1]] = 1; 
    for(int i = 1; i<=m; i++){
        int cur = i&1; 
        int prev = 1-cur;
        sum2 = sum;
        sum = 0;
        for(int j : P){
            DP[cur][j] = ((sum2 - DP[prev][j])%MOD + MOD)%MOD;
            for(int x = head[j]; x!=-1; x=NDS[x].next){ 
                int y = NDS[x].to;
                if(y==j) continue;
                DP[cur][j] = ((DP[cur][j] - DP[prev][y])%MOD + MOD) % MOD;
            }
            sum += DP[cur][j]; 
            sum %= MOD;
        }
        DP[cur][idf] = (1LL * sum2 * Fc % MOD - 1LL * DP[prev][idf] % MOD)%MOD; 
        sum = (sum % MOD + DP[cur][idf] % MOD) % MOD;
    }
    cout << DP[m&1][Dict[1]]%MOD << endl; 
    return 0;
}