I need help with this problem asked in Google Online Challenge.

You are given the following: - An integer value N - M pairs of distinct characters (lowercase English alphabets) A pair of characters in the given pairs holds a relation between them. The relation among the given pairs is also transitive, which means if you consider 2 pairs (u, v) and (v, w) which holds relation, then pair (u, w) also holds the relation. Also, the relation states that those pairs of characters cannot occur together in a formed string. Determine the total number of strings of length N such that any string does not contain a pair of adjacent characters holding any relation. Since this number can be large output it modulo 10^9+7.

Constraints 1 <= T <= 10 (Number of test cases) 1 <= N <= 10^4 0 <= M <= 325 (M is the number of pairs given)

Example Input: N = 2 M = 3 Pairs = [[a,b], [b,c], [c,d]]

Approach: - Since [a,b] and [b,c] hold a transitive relation, thus a relation among all pairs in [a, b, c] holds true. - Since [a, b, c] and [c, d] shares a transitive relation thus a relation among all pairs in [a, b, c, d] holds true. - So the following pairs cannot occur : [ab, ac, ad, ba, bc, bd, ca, cb, cd, da, db, dc] - The strings that can be formed of length 2 are : ["aa", "ae", "af", .....]

Output: 664