[Question]
  [
You may know the game [*The Six Degrees of Kevin Bacon*](https://en.wikipedia.org/wiki/Six_Degrees_of_Kevin_Bacon), based on the conjecture that every actor in Hollywood can be connected to Kevin Bacon by no more than 6 "co-star" relations, so Kevin Bacon is supposedly the "best-connected" node in that graph. Your task will be to find the Kevin Bacon of a graph.
We will use positive integers to represent actors, and use a list of pairs which defines the relations of the graph (adjacency list). For example, `[(1, 2), (2, 3)]` defines that `1` has costarred with `2`, and `2` has costarred with `3`.
We will measure "connectedness" using *average shortest path length*:
* The shortest path length is the number of steps in the shortest path between two given nodes. In the example graph above, the shortest (and also only) path between `1` and `3` is `1 -> 2 -> 3`, which has path length 2
* The average shortest path length of a node `A` is the mean of the shortest path lengths between `A` and each other node in the network
Your task is to, given an adjacency list, find the best-connected node in the graph. That is, find the node `A` such that this average is minimised, and output its number.
If there are multiple nodes with the same average shortest path length, you may output any of them.
## Worked example
Consider the small graph:
```
    1-----2
   / \    |
  3---4   5
```
which would be represented by the adjacency list:
```
[(1, 2), (2, 5), (1, 3), (1, 4), (3, 4)]
```
Now we compute the shortest path length between each pair of nodes (ignoring the relations between nodes and themselves):
```
  |1 2 3 4 5
--+---------
1 |  1 1 1 2
2 |1   2 2 1
3 |1 2   1 3
4 |1 2 1   3
5 |2 1 3 3
```
For each node we can then compute the average of its path lengths to all the other nodes:
```
1 ~> 1.25  [  (1+1+1+2)/4 = 5/4 = 1.25  ]
2 ~> 1.5
3 ~> 1.75
4 ~> 1.75
5 ~> 2.25
```
So node `1` has the smallest average shortest path length, so the output is `1`.
## Rules
* You may assume the input is non-empty, contains no self-referential pairs (like `(3, 3)`), and no duplicate edges (like `[(3, 1), (1, 3)]`)
* You may assume all nodes of the graph are connected somehow (for example, you don't have to handle `[(1, 2), (3, 4), (5, 3)]`)
* You may assume the set of integers used for node IDs is `1` to `N` (inclusive) for some N. For example, you don't have to handle `[(1, 54), (54, 128)]` nor `[(2, 3), (2, 4)]`
	+ You may alternately choose to assume this range is `0` to `N-1`
* You may use any [standard I/O method](https://codegolf.meta.stackexchange.com/q/2447)
* [Standard loopholes](https://codegolf.meta.stackexchange.com/q/1061) are forbidden
* This is [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'"), so the shortest code in bytes wins
## Test cases
```
Input:  [(1, 2), (2, 5), (1, 3), (1, 4), (3, 4)]
Output: 1
Input:  [(1, 2), (2, 3), (3, 4), (4, 5)]
Output: 3
Input:  [(1, 2), (2, 3), (3, 4), (4, 1), (2, 5)]
Output: 2
Input:  [(1, 2)]
Output: 1 or 2
Input:  [(6, 1), (5, 2), (2, 1), (1, 5), (6, 3), (6, 4), (3, 4), (6, 2), (3, 7)]
Output: 6
```
  
[Answer]
# [BQN](https://mlochbaum.github.io/BQN/)\*, ~~53~~ 45 bytes[SBCS](https://github.com/mlochbaum/BQN/blob/master/commentary/sbcs.bqn)
```
{1+‚äë‚çí+Àù+¬¥(‚à®‚à®‚à®Àù‚àò√ó‚éâ1‚Äø‚àû)‚çünÀú‚à®‚üú‚çâ‚à®Àùùï©‚â°‚åú1+‚ãà‚åúÀún‚Üê‚Üï‚åà¬¥‚àæùï©}
```
[Run online!](https://mlochbaum.github.io/BQN/try.html#code=RiDihpAgezEr4oqR4o2SK8udK8K0KOKIqOKIqOKIqMud4oiYw5fijokx4oC/4oieKeKNn27LnOKIqOKfnOKNieKIqMud8J2VqeKJoeKMnDEr4ouI4oycy5xu4oaQ4oaV4oyIwrTiiL7wnZWpfQoKCj7ii4jin5xG4oiY4oCiSnPCqCDin6giW1sxLCAyXSwgWzIsIDVdLCBbMSwgM10sIFsxLCA0XSwgWzMsIDRdXSIKIltbMSwgMl0sIFsyLCAzXSwgWzMsIDRdLCBbNCwgNV1dIgoiW1sxLCAyXSwgWzIsIDNdLCBbMywgNF0sIFs0LCAxXSwgWzIsIDVdXSIKIltbMSwgMl1dIgoiW1s2LCAxXSwgWzUsIDJdLCBbMiwgMV0sIFsxLCA1XSwgWzYsIDNdLCBbNiwgNF0sIFszLCA0XSwgWzYsIDJdLCBbMywgN11dIuKfqQo=)
**Theory:**
Let \$k\$ be the maximum node id. Then the node IDs are \$\{1, 2, ..., k\}\$.  
For the given adjacency list we can construct an adjancency matrix \$A=(a\_{ij}) \in \{0,1\}^{k \times k}\$, where \$a\_{ij} = 1\$ iff \$i=j\$ or node \$i\$ and node \$j\$ are adjacent.
The distance between two nodes in the graph is given by the smallest \$m\$, such \$A^m\$ has a non-zero entry at the position.‚Ä†
**Implementation:**
[`‚à®‚üú‚çâ‚à®Àùùï©‚â°‚åú1+‚ãà‚åúÀún‚Üê‚Üï‚åà¬¥‚àæùï©`](https://mlochbaum.github.io/BQN/try.html#code=RiDihpAge+KIqOKfnOKNieKIqMud8J2VqeKJoeKMnDEr4ouI4oycy5xu4oaQ4oaV4oyIwrTiiL7wnZWpfQoKRiAoMeKAvzIp4oC/KDLigL81KeKAvygx4oC/MynigL8oMeKAvzQp4oC/KDPigL80KQ==)  
Convert the adjacency list to a modified adjacency matrix \$A-I\_k\$ with zeros on the diagonals. This part is a bit lengthy, maybe `‚àä` can be used?
[`(‚à®‚à®‚à®Àù‚àò√ó‚éâ1‚Äø‚àû)‚çünÀú`](https://mlochbaum.github.io/BQN/try.html#code=RiDihpAgeyjiiKjiiKjiiKjLneKImMOX4o6JMeKAv+KIninijZ9uy5ziiKjin5zijYniiKjLnfCdlaniiaHijJwxK+KLiOKMnMucbuKGkOKGleKMiMK04oi+8J2VqX0KCkYgKDHigL8yKeKAvygy4oC/NSnigL8oMeKAvzMp4oC/KDHigL80KeKAvygz4oC/NCk=)  
Calculate \$A-I\_k, \mathop{sign}(A^2), \mathop{sign}(A^3), \cdots, \mathop{sign}(A^{k-1})\$. In [normal matrix multiplication](https://mlochbaum.github.io/bqncrate/?q=matrix%20multiplication%20of#) you would use `+` instead of `‚à®`, but here we only care for zero / non-zero.
[`+Àù+¬¥`](https://mlochbaum.github.io/BQN/try.html#code=RiDihpAgeyvLnSvCtCjiiKjiiKjiiKjLneKImMOX4o6JMeKAv+KIninijZ9uy5ziiKjin5zijYniiKjLnfCdlaniiaHijJwxK+KLiOKMnMucbuKGkOKGleKMiMK04oi+8J2VqX0KCkYgKDHigL8yKeKAvygy4oC/NSnigL8oMeKAvzMp4oC/KDHigL80KeKAvygz4oC/NCk=)  
Sum the resulting \$k\$ matrices, then each row. This is some kind of *inverse summed shortest path length*. This could be converted to the *average shortest path length*, but that step is not necessary as the order is the same, but reversed.
[`1+‚äë‚çí`](https://mlochbaum.github.io/BQN/try.html#code=RiDihpAgezEr4oqR4o2SK8udK8K0KOKIqOKIqOKIqMud4oiYw5fijokx4oC/4oieKeKNn27LnOKIqOKfnOKNieKIqMud8J2VqeKJoeKMnDEr4ouI4oycy5xu4oaQ4oaV4oyIwrTiiL7wnZWpfQoKCj7ii4jin5xG4oiY4oCiSnPCqCDin6giW1sxLCAyXSwgWzIsIDVdLCBbMSwgM10sIFsxLCA0XSwgWzMsIDRdXSIKIltbMSwgMl0sIFsyLCAzXSwgWzMsIDRdLCBbNCwgNV1dIgoiW1sxLCAyXSwgWzIsIDNdLCBbMywgNF0sIFs0LCAxXSwgWzIsIDVdXSIKIltbMSwgMl1dIgoiW1s2LCAxXSwgWzUsIDJdLCBbMiwgMV0sIFsxLCA1XSwgWzYsIDNdLCBbNiwgNF0sIFszLCA0XSwgWzYsIDJdLCBbMywgN11dIuKfqQo=)  
Get the 1-based index of the maximum value. Using 0-indexing for the node IDs would save two bytes.
\*[According to the documentation, in this situation the name can be pronounced *bacon*](https://mlochbaum.github.io/BQN/#what-kind-of-name-is-bqn)  
‚Ä†Slightly longer explanation can be found [on Wikipedia](https://en.wikipedia.org/wiki/Adjacency_matrix#Matrix_powers)
[Answer]
# [Wolfram Language (Mathematica)](https://www.wolfram.com/wolframscript/), 46 bytes
-12 bytes thanks to @att.
```
gÔí°#&@@SortBy[##&@@@g,Tr[g~GraphDistance~#]&]
```
[Try it online!](https://tio.run/##y00syUjNTSzJTE78n6Zg@z/9/aSFymoODsH5RSVOldHKILZDuk5IUXR6nXtRYkGGS2ZxSWJecmqdcqxa7P@Aosy8kmhlBV07hbRo5dhYBTUFfQeF6mpDBRugkJGOghGYYaqjABExhjFMdBSMIYxaHQV05cZwSR0FE4gBRKkyhNuHpBzENINJm6IaYQhzDtCBZjBDzdAcCBMxgomY19b@BwA "Wolfram Language (Mathematica) ‚Äì Try It Online")
Takes input as a list of `a <-> b`s, e.g. `{1 <-> 2, 2 <-> 5, 1 <-> 3, 1 <-> 4, 3 <-> 4}`.
Sadly the `GraphCenter` built-in uses the *maximal* (instead of *average*) shortest path length.
[Answer]
# [J](http://jsoftware.com/), 72 71 73 bytes
```
1+[:(i.<./)1#.[:+/@(*#\)2-~/\0,[:+./ .*^:a:~@(+[:=#\)[:+/](-{.1:)"1@,|."1
```
[Try it online!](https://tio.run/##XY3LCsIwEEX3fsXQCk36mDRpEzFYKAiuXLltFUQs6sYPUPrrcZLiA8lrcubk5uYiTAZoLCSQQwmWVoGw3m03TmadZVdcoeAyxs5momVp3HNVjKIvcwIoANODPdqxZSQ31PTanhUPlJZHss2fGEnHZ@fT5Q4SGhhAg4I51QpoaqCq8lsNdNaTWAWx/oiKCDVp6ElQf0lfwd/073fyLU3QBLgM0BDW4bUMlaEMQxk@yYTMhXsB "J ‚Äì Try It Online")
**Input:** 1-indexed adjacency list.
**Output:** 1-indexed answer.
## how
Consider:
```
1 2
2 5
1 3
1 4
3 4
```
* `[:+/](-{.1:)"1@,|."1` - Converts the adjacency list to an adjacency matrix.
This was the hardest part to golf, and it's still long.
	+ `]...,|."1` First we concatenate the list with a copy of itself, with each row reversed:
	
	
	
	```
	1 2
	2 5
	1 3
	1 4
	3 4
	2 1
	5 2
	3 1
	4 1
	4 3
	
	```
	+ `(-{.1:)"1` - Then we create matrices of each of those sizes, with a `1`
	in the bottom right corner. I'll display them boxed, before the automatic
	0 fill, for clarity:
	
	
	
	```
	‚îå‚îÄ‚îÄ‚îÄ‚î¨‚îÄ‚îÄ‚îÄ‚îÄ‚îÄ‚îÄ‚îÄ‚îÄ‚îÄ‚î¨‚îÄ‚îÄ‚îÄ‚îÄ‚îÄ‚î¨‚îÄ‚îÄ‚îÄ‚îÄ‚îÄ‚îÄ‚îÄ‚î¨‚îÄ‚îÄ‚îÄ‚îÄ‚îÄ‚îÄ‚îÄ‚î¨‚îÄ‚î¨‚îÄ‚îÄ‚îÄ‚î¨‚îÄ‚î¨‚îÄ‚î¨‚îÄ‚îÄ‚îÄ‚îÄ‚îÄ‚îê
	‚îÇ0 1‚îÇ0 0 0 0 0‚îÇ0 0 1‚îÇ0 0 0 1‚îÇ0 0 0 0‚îÇ0‚îÇ0 0‚îÇ0‚îÇ0‚îÇ0 0 0‚îÇ
	‚îÇ   ‚îÇ0 0 0 0 1‚îÇ     ‚îÇ       ‚îÇ0 0 0 0‚îÇ1‚îÇ0 0‚îÇ0‚îÇ0‚îÇ0 0 0‚îÇ
	‚îÇ   ‚îÇ         ‚îÇ     ‚îÇ       ‚îÇ0 0 0 1‚îÇ ‚îÇ0 0‚îÇ1‚îÇ0‚îÇ0 0 0‚îÇ
	‚îÇ   ‚îÇ         ‚îÇ     ‚îÇ       ‚îÇ       ‚îÇ ‚îÇ0 0‚îÇ ‚îÇ1‚îÇ0 0 1‚îÇ
	‚îÇ   ‚îÇ         ‚îÇ     ‚îÇ       ‚îÇ       ‚îÇ ‚îÇ0 1‚îÇ ‚îÇ ‚îÇ     ‚îÇ
	‚îî‚îÄ‚îÄ‚îÄ‚î¥‚îÄ‚îÄ‚îÄ‚îÄ‚îÄ‚îÄ‚îÄ‚îÄ‚îÄ‚î¥‚îÄ‚îÄ‚îÄ‚îÄ‚îÄ‚î¥‚îÄ‚îÄ‚îÄ‚îÄ‚îÄ‚îÄ‚îÄ‚î¥‚îÄ‚îÄ‚îÄ‚îÄ‚îÄ‚îÄ‚îÄ‚î¥‚îÄ‚î¥‚îÄ‚îÄ‚îÄ‚î¥‚îÄ‚î¥‚îÄ‚î¥‚îÄ‚îÄ‚îÄ‚îÄ‚îÄ‚îò
	
	```
	
	Once the fill is added it looks like:
	
	
	
	```
	0 1 0 0 0
	0 0 0 0 0
	0 0 0 0 0
	0 0 0 0 0
	0 0 0 0 0
	
	0 0 0 0 0
	0 0 0 0 1
	0 0 0 0 0
	0 0 0 0 0
	0 0 0 0 0
	
	0 0 1 0 0
	0 0 0 0 0
	0 0 0 0 0
	0 0 0 0 0
	0 0 0 0 0
	.
	.
	.
	
	```
	+ `[:+/` - Finally we sum the layers, giving us the adjacency matrix:
	
	
	
	```
	0 1 1 1 0
	1 0 0 0 1
	1 0 0 1 0
	1 0 1 0 0
	0 1 0 0 0
	
	```
* `(+[:=#\)` Next we add the diagonal of ones (nodes are already connected to themselves).
```
1 1 1 1 0
1 1 0 0 1
1 0 1 1 0
1 0 1 1 0
0 1 0 0 1
```
* `+./ .*^:a:~` Matrix "or multiply" with self, until we reach a fixed point, saving intermediate values. The additional ones added in iteration `n` represent nodes that can be reached in `n` hops.
* `2-~/\0,` We want to separate each iteration's contribution, so we take successive deltas, starting with a matrix of all zeros:
```
1 1 1 1 0
1 1 0 0 1
1 0 1 1 0
1 0 1 1 0
0 1 0 0 1
0 0 0 0 1
0 0 1 1 0
0 1 0 0 0
0 1 0 0 0
1 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 1
0 0 0 0 1
0 0 1 1 0
```
* `(*#\)` Multiply each of those values by its iteration number:
```
1 1 1 1 0
1 1 0 0 1
1 0 1 1 0
1 0 1 1 0
0 1 0 0 1
0 0 0 0 2
0 0 2 2 0
0 2 0 0 0
0 2 0 0 0
2 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 3
0 0 0 0 3
0 0 3 3 0
```
* `+/@` And sum the layers:
```
1 1 1 1 2
1 1 2 2 1
1 2 1 1 3
1 2 1 1 3
2 1 3 3 1
```
* `1#.` Then sum the rows:
```
6 7 8 8 10
```
* `1+[:(i.<./)` Finally return the minimum value's index, plus 1:
```
1
```
[Answer]
# [Python 3](https://docs.python.org/3/), 234 bytes
```
def f(l):
 m=1+max(map(max,l));g=eval(str([[m]*m]*m))
 for a,b in l:g[a][a]=g[b][b]=0;g[a][b]=g[b][a]=1
 for x in range(m**3):k=x%m;x//=m;j=x%m;i=x//m;g[j][k]=min(g[j][k],g[j][i]+g[i][k])
 return min((sum(g[i]),i)for i in range(m))[1]
```
[Try it online!](https://tio.run/##TU7NDoMgDL77FFyWUGfijDcNT0I4YKYMtWhQF/b0rDgPS762X3@/rp/9tbg6xmc/sIHP0GQMRXVHHTjqlSwUM0BrRP/WM992z6VElScAZGxYPNNFx6xjc2OkVgRhZKcI4tGele6qUKf6bYQ077UzPcc8r6GZRLhhG8pSYDue3ArKkA6MSk5KoHX84sUZrbobcpTTF77fD@9YGuLbgTx1oLCQtOyfFoCsVIxf "Python 3 ‚Äì Try It Online")
Implementing simple Floyd-Warshall. This is my first time here. Any tips are welcome!
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 27 [bytes](https://github.com/DennisMitchell/jelly/wiki/Code-page)
```
;¬©U;√æ¬Æ·∫é·∏¢‚Åº·π™∆ä∆á∆äL√ê¬°≈í·π¨‚Ç¨ƒñP‚Ç¨o/Sƒ∞M
```
A monadic Link accepting the adjacency list specified that yields a list of all of the Kevin Bacons of that graph.
**[Try it online!](https://tio.run/##y0rNyan8/9/60MpQ68P7Dq17uKvv4Y5Fjxr3PNy56ljXsfZjXT6HJxxaeHTSw51rHjWtOTItAEjm6wcf2eD7////aA1DHQUjTR0FDSMdBWMQbayjYAKiTXQUDKHippqxAA "Jelly ‚Äì Try It Online")**
How?
We first produce lists of all pairs of nodes linked by `1, 2, 3, ...` steps (up to `2p+1` where `p` is the number of pairs in the input, just for golfing purposes) - including redundancies and self-linked pairs.
Then we turn each of these into tables showing the number of steps taken, if possible, or zero if not - i.e. the first is `0` or `1` at each point, the second is `0` or `2` at each point, and so on.
We then reduce these by logical OR, giving us the shortest length table shown in the question with a leading diagonal filled with `2`s (since we are guaranteed a fully-connected graph, we will always produce a `2` at this position in the second previous table by following a given pair and its reverse, and the logical OR will keep this value if we could do the same in more steps).
Then we sum the columns, inverse and find maximal indices (aligning with the guaranteed `[1,n]` node numbering).
```
;¬©U;√æ¬Æ·∫é·∏¢‚Åº·π™∆ä∆á∆äL√ê¬°≈í·π¨‚Ç¨ƒñP‚Ç¨o/Sƒ∞M - Link: adjacency list, A
  U                         - reverse each pair in A
;                           - concatenate that to A
 ¬©                          - copy this to the register for later
              √ê¬°            - collect up and repeat:
             L              - ...times: length (of the new list)
            ∆ä               - ...what: the last three links as a monad, f(current):
     ¬Æ                      -     use the register as the right argument of:
    √æ                       -       (current) table (register) using:
   ;                        -         concatenation (e.g. [2,5];[1,2] -> [2,5,1,2])
      ·∫é                     -     tighten (from a table to a row-major order list)
           ∆á                -     filter keep those for which:
          ∆ä                 -       last three links as a monad:
       ·∏¢                    -         pop and yield head
         ·π™                  -         pop and yield tail
        ‚Åº                   -         equal? (leaving the inner two
                                              e.g. [2,5,1,2] -> [5,1]
                                              which is kept since 2=2)
                  ‚Ç¨         - for each:
                ≈í·π¨          -   make a table with 1s at the given coordinates)
                   ƒñ        - enumerate -> [[1,first],[2,second],...]
                    P‚Ç¨      - product of each
                      o/    - reduce by logical OR
                        S   - sum columns
                         ƒ∞  - inverse
                          M - maximal indices (1-indexed)
```
[Answer]
# [R](https://www.r-project.org/), ~~120~~ ~~113~~ ~~111~~ ~~107~~ ~~106~~ 102 bytes
Or **[R](https://www.r-project.org/)>=4.1, 95 bytes** by replacing the word `function` with a `\`.
*Edit: -7 bytes and -4 bytes thanks to [@Giuseppe](https://codegolf.stackexchange.com/users/67312/giuseppe). -1 byte thanks to [@Dominic van Essen](https://codegolf.stackexchange.com/users/95126/dominic-van-essen). -4 bytes inpired by [@Dominic van Essen's answer to related challenge](https://codegolf.stackexchange.com/a/245389/55372).*
```
function(v){A=diag(m<-max(v))
A[v]=1
C=B=A=A|t(A)
for(i in 2:m)B[(C=C%*%A)&!B]=i
order(colSums(B))[1]}
```
[Try it online!](https://tio.run/##jY9BC4JAFITv@ys2wngv7LBrGUR7WP0BHTqKh9KMhXRjUwmq325ZLWl06DYMb755Y5pMNFlVJKXSBdR4kSJVmz3ky0m@OT8MJDKqY8FIKAIhhbyWIJFk2oCiqqB8kWMQQShCZ@xIHA2CWCiiTbozkOjDuspPECBGLL41GZitKlJIgLmUo0sT4C6dPcXD8ayYPoXXCkQ6XFXlsSoXlJHfAO9z3oppi@zmvL9z7PNTF8C/Ab2vqDa9C99yZp0uZre91vq23e@tfTvcOvNek9/cAQ "R ‚Äì Try It Online")
Straightforward approach:
1. Calculate adjacency matrix `A`.
2. Gradually increase powers of `A` (stored in `C`) to see when will appear the first non-zero entry for each pair of indices. *(Where's built-in matrix power when you need one?)*
3. Store the distances in `B`.
4. Find the column with the smallest sum.
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E/wiki/Commands), ~~44~~ 42 [bytes](https://github.com/Adriandmen/05AB1E/wiki/Codepage)
[*I guess crossed out 44 is no longer a thing with the new font. ;)*](https://codegolf.stackexchange.com/questions/170188/crossed-out-44-is-still-regular-44)
```
ZL¬©Œµ¬ÆyKŒ¥‚ÄöŒµU√¶‚Ç¨≈ì‚Ç¨` í–ΩX–Ω√•yŒ∏XŒ∏√•y√º√•‚Ç¨√†PP}‚Ç¨g√ü]OWk>
```
Takes advantage of the rule "*You may assume the set of integers used for node IDs is positive and contiguous.*" to save some bytes, although it still feels pretty long..
[Try it online](https://tio.run/##yy9OTMpM/f8/yufQynNbD62r9D635VHDrHNbQw8ve9S05uhkIJFwatKFvREX9h5eWnluR8S5HUD68J7DS4EyhxcEBNQC6fTD82P9w7Pt/v@PjjbUMYrViTbSMQWShjrGYNIESBoDyVgA) or [verify almost all test cases](https://tio.run/##yy9OTMpM/V9Waa@k8KhtkoKSfaVLmNL/KJ9DK89tPbSu0vvclkcNs85tDY08vOxR05qjk4FEwqlJF/ZGXNh7eGnluR0R53YA6cN7Di8FyhxeEBBQC6TTD8@P9Q/PtvuvpBem8z86OtpQxyhWJ9pIxxRIGuoYg0kTIGkMJGN1FBAKjKGCOtEmQMU4pQyhpsEVxMYCAA) (the largest/last test case times out and is omitted in the test suite).
**Explanation:**
```
Z            # Get the flattened maximum of the (implicit) input-list of pairs
 L           # Pop and push a list in the range [1,max]
  ¬©          # Store it in variable `¬Æ` (without popping)
   Œµ         # Map over each integer:
    ¬Æ        #  Push the [1,max] list from variable `¬Æ` again
     yK      #  Remove the current integer from it
       Œ¥     #  Map over each remaining integer:
        ‚Äö    #   Pair it with the current integer
    Œµ        #  Map over each pair:
     U       #   Pop the current pair and store it in variable `X`
      √¶      #   Get the powerset of the (implicit) input-list of pairs
       ‚Ç¨≈ì    #   Get the permutations of each inner list
         ‚Ç¨`  #   Flatten it one level down
      í       #   Filter over this list of potential paths:
      –Ω      #    Pop and push the first pair
       X–Ω√•   #    Check if the first value of `X` is in this pair
      yŒ∏XŒ∏√•  #    Do the same for the last pair and last value of `X`
      y      #    Then push the list of pairs again
       √º     #    For each overlapping pair of pairs:
        √•    #     Check for both values in the second pair if it's in the first
             #    (this will result in an empty list for single-pair lists)
         ‚Ç¨√†  #    Check for each overlapping check if either is truthy
           P #    Check if all overlapping checks are truthy
      P      #    Check if all three checks are truthy
     }‚Ç¨g     #   After the filter: get the length of each valid path
        √ü    #   Pop and push the minimum path-length
   ]         # Close both the inner and outer maps
    O        # Sum each inner list (shorter than the average)
     W       # Push the minimum sum (without popping the list)
      k      # Get the (first) 0-based index of this minimum
       >     # Increase it by 1 to make it a 1-based index
             # (after which this is output implicitly as result)
```
[Answer]
# [Charcoal](https://github.com/somebody1234/Charcoal), ~~82~~ 81 bytes
```
‚âî‚äï‚åàÔº•Œ∏‚åàŒπŒ∑‚âîÔº•Œ∑Ôº•Œ∑‚à®‚ÅºŒπŒª‚à®‚ÑñŒ∏‚ü¶ŒπŒª‚üß‚ÑñŒ∏‚ü¶ŒªŒπ‚üßŒ∑‚âîÔº•Œ∑ŒπŒ∂‚âîÔº•Œ∑ŒπŒµÔº¶Œ∑¬´ÔºµÔº≠Œ∂Ôº•Œ∫‚äôŒ∑‚àß¬ßŒ∫œÄ¬ßŒæŒΩÔºµÔº≠ŒµÔº•Œ∫‚Å∫Œº¬ß¬ßŒ∂ŒªŒΩ¬ªÔºµÔº≠ŒµŒ£ŒπÔº©‚åïŒµ‚åàŒµ
```
[Try it online!](https://tio.run/##dZAxa8MwEIXn@lfcKIMKSZp08WRMAxlCAx2NBmGrtagkJ5JdXJf@dvVkyw2BVsvjvrv3JF3VcFu1XHmfOyffDDmYygotTCdqcuSD1L1GPZMLhaWUKR4KTZol0RQGmjAwybMlT5eeK0ckBZVOoGh704WQMjCG8EoUBcnS/0Il0vFPKpC@thZIk8JXcoedotWam5qM81veKeTmM4znCPPuYGoxBHpG91IOFMx0eXYTIX4jTqp3RF8Ni47z58zs/U5uzS/zorLkZCX@s@CuI3u5BM@LFJPV@7IsdxRWDHexpbAOuo71isI2KPY3UR@CbqLu4jzWj4wxf/@hfgA "Charcoal ‚Äì Try It Online") Link is to verbose version of code. Explanation: Port of ovs's "Bacon" answer.
```
‚âî‚äï‚åàÔº•Œ∏‚åàŒπŒ∑
```
Get the number of nodes.
```
‚âîÔº•Œ∑Ôº•Œ∑‚à®‚ÅºŒπŒª‚à®‚ÑñŒ∏‚ü¶ŒπŒª‚üß‚ÑñŒ∏‚ü¶ŒªŒπ‚üßŒ∑
```
Calculate the adjacency matrix.
```
‚âîÔº•Œ∑ŒπŒ∂‚âîÔº•Œ∑ŒπŒµ
```
Create two shallow clones as we'll be mutating these.
```
Ôº¶Œ∑¬´
```
Repeat for each node, to ensure that all nodes are eventually reached.
```
ÔºµÔº≠Œ∂Ôº•Œ∫‚äôŒ∑‚àß¬ßŒ∫œÄ¬ßŒæŒΩ
```
Update the first clone to the adjacency matrix at the next depth.
```
ÔºµÔº≠ŒµÔº•Œ∫‚Å∫Œº¬ß¬ßŒ∂ŒªŒΩ
```
Add it to the second clone.
```
¬ªÔºµÔº≠ŒµŒ£Œπ
```
Sum the rows of the second clone.
```
Ôº©‚åïŒµ‚åàŒµ
```
Find the index of the largest sum.
[Answer]
# [Perl 5](https://www.perl.org/) List::Util, 174 bytes
```
sub{$S=99;sub D{$_[0]-$a?1+min map D(@$_),grep$_[0]==$$\_[1]&&!$b{$$_[0]}++,@g:0}for$a(@a=uniq map@$_,@g=map{$_,[@$_[1,0]]}@_){$S=$s,$A=$a if$S>($s=sum map{%b=();D($_)}@a)}$A}
```
[Try it online!](https://tio.run/##jVJNb5tAED2XXzFJxzZbb2uDY1cBbUIkbqmSQ9oTQdamXdCqARMWlFYO@evuLKCkSi/dy3vz8ebtV6Xq@/WhNQq@aNMEwbdG38PDo9uW@gEKXYJpCxY6tiGWjQyCuC0qVYcOZuJg2rs93ojT05AYxHvcJsv0I8pzb26lhawgdiPcMp7XquqrQiChl06nR0jiPtfN5zzKg2WX7WqUbiTF4C4r0lJFEKPZPImslC/TtIu2zDqj4XghUILO8ObMRSNou1a4n9wJl4WxS@ZdJFmHF90hdMjAdRKAhMaAn3JIfA5rixSvRjyxuLKYgjgDDyDl/4hWL02EJ3ZI37z6r2bvxbkX@W9Eoy01vd/V4A@VzShbv471xg33B9iMNpu/DzDE/hh/HiZveju2d4BW8dtFzVExQZcbjinMxRQzejnNhlRV67LJjieGuPpVqe@N@hEAKgrzXUMsJ6bLqiU@MbflMXfeoaK3zuEcZrufMwhgdnX9Fa4vZxyGL0S@TDybxacP4unWPIWLRU7fqjv8AQ "Perl 5 ‚Äì Try It Online")
[Answer]
# Python3, 276 bytes:
```
lambda g:min(enumerate(n:=[*{i for k in g for i in k}]),key=lambda x:sum(min(p(g,x[1],j))for j in n[:x[0]]+n[x[0]+1:])/float(len(n)-1))[1]
def p(g,s,e,c=[]):
 if s==e:yield len(c)
 else:
  for i in g:
   if s in i and(j:=[i[0],i[1]][s==i[0]])not in c:yield from p(g,j,e,c+[s])
```
[Try it online!](https://tio.run/##jU/LToQwFN3zFXfZ69QoMIOmCV9Su8ChxfIoBJgEYvx27MVmRpNZuDo97Xl1WOeP3qWvw7iZ/G1ri@69LKASnXVMu0unx2LWzIlcPnxaMP0IDVgH1X60dGy@FPJGr3nwLmK6dIz8A6v4ImPFa0SS1yR3UizyWamDk4SHWCh8Mm1fzKzVjjl8jBG9KSq1AUqYuObnXCoUEVgDU55rsVrdlkD6M0ag20n7x9ukitguJmahcCWr/ResL@TWhyvpY4gpdP1MonPINGPf7bU11R7kpHAbRutmZphkMYcEObCEw4nQ8zTgkTAlVIjRXUt6lXg8UsS/pfG19Y7l71UW1KdbWhw27puzkJ793vzDk8BfKHL7Bg)
]